package Medium;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class LC0649 {
    /**
     * 这题的一个“陷阱”在于，当一个参议员有投票的权利时，应该优先消灭后面的对方参议员，因为后面的参议员在这一轮仍然能够行使权利。
     */
    public String predictPartyVictory(String senate) {
        char[] senates = senate.toCharArray();
        int length = senates.length;
        while (true) {
            for (int i = 0; i < length; i++) {
                if (senates[i] == 'B') continue;
                boolean banFlag = false;
                if (senates[i] == 'R') {
                    for (int j = 0; j < length - 1; j++) {
                        int idx = (j + 1 + i) % length;
                        if (senates[idx] == 'D') {
                            senates[idx] = 'B';
                            banFlag = true;
                            break;
                        }
                    }
                    if (!banFlag) return "Radiant";
                }
                else {
                    for (int j = 0; j < length - 1; j++) {
                        int idx = (j + 1 + i) % length;
                        if (senates[idx] == 'R') {
                            senates[idx] = 'B';
                            banFlag = true;
                            break;
                        }
                    }
                    if (!banFlag) return "Dire";
                }
            }
        }
    }

    /**
     * 官方解法，使用两个队列存储双方尚且有资格的参议员。参议员有一个时间戳，表示参议员行使权利的时机。在每次循环的开始，检查两个队列队首议员的时间戳，
     * 以确定行使权利的议员。行使权利的议员可以弹出对方队列的队首议员，将自己的时间戳+N再放回队列。如果一方的队列为空，则另一方胜利。
     * 官方题解的性能优于自己的题解。
     */
    public String predictPartyVictoryOfficial(String senate) {
        Queue<Integer> radiantQueue = new LinkedList<>(), direQueue = new LinkedList<>();
        int N = senate.length();
        for (int i = 0; i < N; i++) {
            char ch = senate.charAt(i);
            if (ch == 'R') radiantQueue.add(i);
            else direQueue.add(i);
        }

        while (!radiantQueue.isEmpty() && !direQueue.isEmpty()) {
            int radiantHead = radiantQueue.poll();
            int direHead = direQueue.poll();
            if (radiantHead < direHead)
                radiantQueue.add(radiantHead + N);
            else direQueue.add(direHead + N);
        }

        if (radiantQueue.isEmpty()) return "Dire";
        else return "Radiant";
    }
}
